package com.google.codejam.minimumscalarproduct;

import com.google.codejam.core.test.ACodeJamTestCase;

import java.util.Arrays;

/**
 * Concrete implementation of the <code>ACodeJamTestCase</code> for the
 * "Minimum Scalar Product" problem.
 */
public class MinimumScalarProductTestCase extends ACodeJamTestCase
{
	private int[] int_array_1;
	private int[] int_array_2;
	private int   number_of_integers;
	private long  result;

	private static final String SEPARATOR = " ";

	public MinimumScalarProductTestCase(int number_of_integers)
	{
		this.number_of_integers = number_of_integers;
	}

	/**
	 * Parses the passed string to extract the data. The first time this method
	 * is called we instantiate the first array of integers. The second time this
	 * method is called we instantiate the second array of integers. Any
	 * subsequent calls to this methods will do nothing, as the integer arrays
	 * are already initialized.
	 *
	 * @param data_str <code>String</code> containing data to be parsed.
	 */
	@Override
	public void parseDataString(String data_str)
	{
		if (int_array_1 == null)
		{
			int_array_1 = initList(data_str);
			return;
		}

		if (int_array_2 == null)
		{
			int_array_2 = initList(data_str);
		}
	}

	/**
	 * Solves this test case. The following steps are performed to solve the test
	 * case:
	 * <ol>
	 *    <li>Sort both arrays in ascending order.</li>
	 *    <li>Iterate through the arrays and do the following -
	 *       <ul>
	 *          <li>multiply, on the first iteration, the first element of the
	 *          first array with the last element of the second array</li>
	 *          <li>on the second iteration, multiply the second element of the
	 *          first array with the second last element of the second array</li>
	 *          <li>and so on and so forth, till you have iterated over all the
	 *          elements of the respective arrays</li>
	 *          <li>on each iteration calculate the sum (as <code>long</code>) of
	 *          each multiplication between the elements of the arrays</li>
	 *       </ul>
	 *    </li>
	 * </ol>
	 */
	@Override
	public void solve()
	{
		Arrays.sort(int_array_1);
		Arrays.sort(int_array_2);

		result = 0;

		for (int i = 0; i < number_of_integers; i++)
		{
			// result = sum of the elements in the first array (sorted in ascended
			// order) multiplied with the corresponding elements in the second
			// array (sorted descending)
			result += (long) int_array_1[i] *
					  (long) int_array_2[(number_of_integers - 1) - i];
		}
	}

	@Override
	public String getResultString()
	{
		return super.getResultString() + result;
	}

	/**
	 * Initialize an array of integers using the passed, space delimited string
	 * of values.
	 *
	 * @param data_str <code>String</code> containing the values to parse.
	 * @return
	 */
	private int[] initList(String data_str)
	{
		if (data_str == null || "".equals(data_str))
		{
			// can't initialize with no data
			return null;
		}

		int[] int_array = new int[number_of_integers];

		String[] integer_str_array = data_str.split(SEPARATOR);

		for (int i = 0; i < number_of_integers; i++)
		{
			int_array[i] = Integer.parseInt(integer_str_array[i]);
		}

		return int_array;
	}
}
